//#include <iostream>
//using namespace std;
//
//int main()
//{
//	int n, k;
//	cin >> n >> k;
//	int ret = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		int x;
//		cin >> x;
//		if (x >= k)
//			ret++;
//	}
//	cout << ret << endl;
//	return 0;
//}

#define _CRT_SECURE_NO_WARNINGS

//#include <iostream>
//#include <unordered_map>
//using namespace std;
//
//const int N = 1e5 + 10;
//const int M = 1e6 + 10;
//int a[N] = { 0 };
//bool st[M] = { 0 };
//
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	unordered_map<int, int> mp;
//	for (int i = 1; i <= n; i++)
//	{
//		scanf("%d", &a[i]);
//		
//		mp[a[i]]++;
//
//		while (mp[a[i]] > 1)
//		{
//			mp[a[i]]--;
//			mp[++a[i]]++;
//		}
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		cout << a[i] << " ";
//	}
//	return 0;
//}

//#include <iostream>
//using namespace std;
//
//const int N = 2e5 + 10;
//
//
//int main()
//{
//	int n, l, r;
//	cin >> n >> l >> r;
//	for (int i = 1; i <= n; i++)
//	{
//		int x;
//		cin >> x;
//		if (x >= l && x <= r)
//			cout << x << " ";
//		else if (x < l)
//			cout << l << " ";
//		else
//			cout << r << " ";
//	}
//	return 0;
//}

//
//#include <iostream>
//using namespace std;
//typedef long long ll;
//const int N = 1e5 + 10;
//ll a[N] = { 0 };
//ll b[N] = { 0 };
//int main()
//{
//	int n;
//	int k;
//	cin >> n >> k;
//	ll sum = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		ll x;
//		cin >> x;
//		sum += x;
//		if (sum >= k)
//			a[sum % k]++;
//		else
//			b[sum % k]++;
//	}
//	long long ret = 0;
//	ret += a[0];
//	ret += a[0] * (a[0] - 1) / 2;
//
//	for (int i = 1; i < k; i++)
//	{
//		ret += a[i] * b[i];
//		ret += a[i] * (a[i] - 1) / 2;
//	}
//
//	cout << ret << endl;
//	
//	return 0;
//}

//#include <iostream>
//#include <algorithm>
//using namespace std;
//
//const int N = 2e5 + 10;
//int a[N] = { 0 };
//int b[N] = { 0 };
//
//int main()
//{
//	int n, m;
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> a[i];
//		b[i] = a[i];
//	}
//
//	sort(b + 1, b + 1 + n);
//	for (int i = 1; i <= m; i++)
//	{
//		int x, y;
//		cin >> x >> y;
//		int aaa = a[x];
//		
//	}
//	return 0;
//}

//
//#include <iostream>
//#include <algorithm>
//using namespace std;
//typedef long long ll;
//const int N = 1e5 + 10;
//
//int n, m;
//ll f[N] = { 0 };
//
//int main()
//{
//	cin >> n >> m;
//	ll x;
//	cin >> x;
//	for (int i = 1; i < m; i++)
//	{
//		ll y;
//		cin >> y;
//		int mini = min(x, y);
//		int maxi = max(x, y);
//
//		f[mini]++;
//		f[maxi]--;
//
//		x = y;
//	}
//	
//	long long ret = 0;
//	for (int i = 1; i < n; i++)
//	{
//		f[i] = f[i] + f[i - 1];
//		ll a, b, c;
//		cin >> a >> b >> c;
//		ret += min(f[i] * a, f[i] * b + c);
//	}
//	cout << ret << endl;
//	return 0;
//}

//#include <iostream>
//#include <vector>
//using namespace std;
//
//int n;
//vector<int> path;
//bool st[10] = { 0 };
//int num;
//int _count = 0;
//
//void dfs()
//{
//	if (path.size() == n)
//	{
//		_count++;
//		int sum = 0;
//		for (auto ch : path)
//		{
//			sum *= 10;
//			sum += ch;
//		}
//		if (sum == num)
//			cout << _count << endl;
//
//		return;
//	}
//
//	for (int i = 1; i <= n; i++)
//	{
//		if (!st[i])
//		{
//			st[i] = 1;
//			path.push_back(i);
//			dfs();
//			path.pop_back();
//			st[i] = 0;
//		}
//	}
//}
//
//int main()
//{
//	cin >> n >> num;
//
//	dfs();
//	return 0;
//}